前置知识：哥德巴赫猜想：任一大于2的偶数都可写成两个质数之和
然后，这道题就非常水了。
令 , 我们分类讨论 的情况就好了。
1. 为一个质数
这时将所有数加起来，分为一个区间。
2.
根据哥猜，我们将 分解为两个质数，分别标记。
这里有一个小结论： 分成的两个质数中，有一个小质数一定小于 。
至于证明，用计算机暴力吧（)
3.
(1)为一个质数，分为两个区间:与
(2)不然，将 , 它是一个偶数，按情况2分解，这时需要三个区间，3 和 哥猜分出的两个质数。
#include <cstdio>
const int MAXN = 6000;
int n , sum , belong[ MAXN + 5 ];
bool zs( int x ) {
if( x == 1 ) return 0;
for( int i = 2 ; i * i <= x ; i ++ )
if( x % i == 0 ) return 0;
return 1;
}
void Make( int x ) { //将一个数分解成两个质数之和
for( int i = 2 ; i <= n ; i ++ )
if( belong[ i ] == 1 && zs( i ) && zs( x - i ) ) {
belong[ i ] = 2;
return;
}
}
int main( ) {
scanf("%d",&n);
sum = n * ( n + 1 ) / 2;
for( int i = 1 ; i <= n ; i ++ )
belong[ i ] = 1;
if( zs( sum ) )
1;
else if( sum % 2 == 0 )
Make( sum );
else {
if( zs( sum - 2 ) )
belong[ 2 ] = 2;
else
belong[ 3 ] = 3 , Make( sum - 3 );
}
for( int i = 1 ; i < n ; i ++ )
printf("%d ",belong[ i ]);
printf("%d",belong[ n ]);
return 0;
}
